// Permutation (排列)
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<vector<int>> permutations; // []
// array 求排列的数组
// current 当前排列
void helper(vector<int> array, vector<int> current) {
  if (array.size() == 0) {
    permutations.push_back(current);
  }
  else {
    for (int i = 0; i < array.size(); ++i) {
      // 找到除了位置 i 之外的，其他元素构成的小数组
      // array[i]
      vector<int> newArray;
      newArray.insert(newArray.end(), array.begin(), array.begin() + i);
      newArray.insert(newArray.end(), array.begin() + i + 1, array.end());

      vector<int> tmp = current;
      tmp.push_back(array[i]);

      helper(newArray, tmp);
    }
  }
}


vector<vector<int>> permutation(vector<int> array) {
  helper(array, {});

  return permutations;
}


int main(int argc, char const *argv[])
{
  /* code */
  vector<int> array{1, 2, 3};
  auto result = permutation(array);

  for (auto arr : result) {
    cout<<"[";
    for (auto n : arr) {
      cout<<n<<" ";
    }
    cout<<"]";
  }

  cout<<endl;
  return 0;
}
